package _11_整理题目._2_二叉树_递归_dfs_bfs._遍历;


import org.junit.Test;
import util.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
 *
 * 给定一个二叉树的根节点 root ，返回它的 中序 遍历。
 *
 * 非递归 迭代写法：
 *      方法一的递归函数我们也可以用迭代的方式实现，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，
 *      而我们在迭代的时候需要显式地将这个栈模拟出来，其他都相同，具体实现可以看下面的代码。
 *
 *      空间复杂度和递归写法一样 O(n)
 */
public class _021_中序非递归遍历 {
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> result = new ArrayList<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            result.add(root.val);
            root = root.right;
        }
        return result;
    }

    @Test
    public void main() {
        Integer[] integer = {1, 2, 3, 4, 5, 6, 7};
        TreeNode root = TreeNode.getTreeFromArray(integer);
        System.out.println(inorderTraversal(root));
    }

    public void inOrder(TreeNode root, List<Integer> list) {
        if (root==null) return;
        inOrder(root.left, list);
        list.add(root.val);
        inOrder(root.right, list);
    }
}
